#include<iostream>
using namespace std;
#include<vector>
#include<list>
#include<algorithm>

//class Solution {
//public:
//    void sortColors(vector<int>& nums) {
//        int i = 0, left = -1, right = nums.size();
//        while (i < right)
//        {
//            if (nums[i] == 0)
//            {
//                swap(nums[++left], nums[i++]);
//            }
//            else if (nums[i] == 2)
//            {
//                swap(nums[i], nums[--right]);
//            }
//            else
//            {
//                i++;
//            }
//        }
//    }
//};
//class Solution {
//public:
//    int GetRandom(vector<int>& nums, int left, int right)
//    {
//        int r = rand();
//        return nums[r % (right - left + 1) + left];  
//    }
//    void Sort(vector<int>& nums, int begin, int end)
//    {
//        if (begin >= end) return;
//        int key = GetRandom(nums, begin, end);
//        int i = begin, left = begin - 1, right = end + 1;
//        while (i < right)
//        {
//            if (nums[i] < key)
//            {
//                swap(nums[++left], nums[i++]);
//            }
//            else if (nums[i] > key)
//            {
//                swap(nums[--right], nums[i]);
//            }
//            else
//            {
//                i++;
//            }
//        }
//        Sort(nums, begin, left);
//        Sort(nums, right, end);
//    }
//    vector<int> sortArray(vector<int>& nums) {
//        srand(time(NULL));
//        Sort(nums, 0, nums.size() - 1);
//        return nums;
//    }
//};

//class Solution {
//public:
//    int reversePairs(vector<int>& record) {
//        int cnt = 0;
//        for (int left = 0; left < record.size(); left++)
//        {
//            for (int right = left + 1; right < record.size(); right++)
//            {
//                if (record[left] > record[right]) cnt++;
//            }
//        }
//        return cnt;
//    }
//};